Thanks for your reply Sandeep , what you suggest was part of the answer . I solved my issue by applying the following :
1- The user of the web service application pool (Identity) should not have an admin privilege and must only have the below rights :

2- The web.config of the web service must include the below parts under the configuration section (So that the web service can Identify the workflow and the items added by it cause the workflow to start): Hint : This part is taken of the web.config of the sharepoint site itself
<configSections>
<sectionGroup name="System.Workflow.ComponentModel.WorkflowCompiler" type="System.Workflow.ComponentModel.Compiler.WorkflowCompilerConfigurationSectionGroup, System.Workflow.ComponentModel, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35">
<section name="authorizedTypes" type="System.Workflow.ComponentModel.Compiler.AuthorizedTypesSectionHandler, System.Workflow.ComponentModel, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" />
<section name="authorizedRuleTypes" type="System.Workflow.ComponentModel.Compiler.AuthorizedTypesSectionHandler, System.Workflow.ComponentModel, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" />
</sectionGroup>
</configSections>
<System.Workflow.ComponentModel.WorkflowCompiler>
<authorizedTypes>
<targetFx version="v4.0">
<authorizedType Assembly="System.Workflow.Activities, Version=3.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="*" Authorized="True" />
<authorizedType Assembly="System.Workflow.Activities, Version=3.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="WhileActivity" Authorized="False" />
<authorizedType Assembly="System.Workflow.Activities, Version=3.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="ConditionedActivityGroup" Authorized="False" />
<authorizedType Assembly="System.Workflow.Activities, Version=3.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="ReplicatorActivity" Authorized="False" />
<authorizedType Assembly="System.Workflow.ComponentModel, Version=3.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="*" Authorized="True" />
<authorizedType Assembly="System.Workflow.ComponentModel, Version=3.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="WorkflowCompiler" Authorized="False" />
<authorizedType Assembly="System.Workflow.Runtime, Version=3.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.Runtime" TypeName="CorrelationToken" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="Guid" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="DateTime" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="Boolean" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="Double" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="String" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Collections" TypeName="Hashtable" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Collections" TypeName="ArrayList" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Diagnostics" TypeName="DebuggableAttribute" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Runtime.CompilerServices" TypeName="CompilationRelaxationsAttribute" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Runtime.CompilerServices" TypeName="RuntimeCompatibilityAttribute" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="Int32" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="TimeSpan" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Collections.ObjectModel" TypeName="Collection`1" Authorized="True" />
<authorizedType Assembly="System.Workflow.Activities, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="*" Authorized="True" />
<authorizedType Assembly="System.Workflow.Activities, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="WhileActivity" Authorized="False" />
<authorizedType Assembly="System.Workflow.Activities, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="ConditionedActivityGroup" Authorized="False" />
<authorizedType Assembly="System.Workflow.Activities, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="ReplicatorActivity" Authorized="False" />
<authorizedType Assembly="System.Workflow.ComponentModel, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="*" Authorized="True" />
<authorizedType Assembly="System.Workflow.ComponentModel, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.*" TypeName="WorkflowCompiler" Authorized="False" />
<authorizedType Assembly="System.Workflow.Runtime, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35" Namespace="System.Workflow.Runtime" TypeName="CorrelationToken" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="Guid" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="DateTime" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="Boolean" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="Double" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="String" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Collections" TypeName="Hashtable" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Collections" TypeName="ArrayList" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Diagnostics" TypeName="DebuggableAttribute" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Runtime.CompilerServices" TypeName="CompilationRelaxationsAttribute" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Runtime.CompilerServices" TypeName="RuntimeCompatibilityAttribute" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="Int32" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System" TypeName="TimeSpan" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Collections.ObjectModel" TypeName="Collection`1" Authorized="True" />
<authorizedType Assembly="Microsoft.SharePoint, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.SharePoint.Workflow" TypeName="SPWorkflowActivationProperties" Authorized="True" />
<authorizedType Assembly="Microsoft.SharePoint, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.SharePoint.Workflow" TypeName="SPWorkflowTaskProperties" Authorized="True" />
<authorizedType Assembly="Microsoft.SharePoint, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.SharePoint.Workflow" TypeName="SPWorkflowHistoryEventType" Authorized="True" />
<authorizedType Assembly="Microsoft.SharePoint, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.SharePoint.Workflow" TypeName="SPItemKey" Authorized="True" />
<authorizedType Assembly="Microsoft.SharePoint, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.SharePoint.Workflow" TypeName="SPWorkflowUserContext" Authorized="True" />
<authorizedType Assembly="Microsoft.SharePoint.WorkflowActions, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.SharePoint.WorkflowActions" TypeName="*" Authorized="True" />
<authorizedType Assembly="Microsoft.Office.Access.Server.Application, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.Office.Access.Server.Macro.Runtime" TypeName="*" Authorized="True" />
<authorizedType Assembly="Microsoft.Office.Access.Server.Application, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.Office.Access.Server.Quickflow.Runtime" TypeName="*" Authorized="True" />
<authorizedType Assembly="Microsoft.Office.Workflow.Actions, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.Office.Workflow.Actions" TypeName="*" Authorized="True" />
</targetFx>
</authorizedTypes>
<authorizedRuleTypes>
<targetFx version="v4.0">
<authorizedType Assembly="Microsoft.Office.Access.Server.Application, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.Office.Access.Server.Quickflow.Runtime" TypeName="*" Authorized="True" />
<authorizedType Assembly="Microsoft.SharePoint.WorkflowActions, Version=15.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c" Namespace="Microsoft.SharePoint.WorkflowActions" TypeName="WorkflowCodeTypeReferenceExpression" Authorized="True" />
<authorizedType Assembly="System.Core, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Runtime.CompilerServices" TypeName="ExtensionAttribute" Authorized="True" />
<authorizedType Assembly="mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Runtime.CompilerServices" TypeName="ExtensionAttribute" Authorized="True" />
</targetFx>
</authorizedRuleTypes>
</System.Workflow.ComponentModel.WorkflowCompiler>
3- The user to add the items to the SharePoint list in the code should not have an identity as an administrator but must be as well a site owner.
4- The code that add the items should not run with administrated privileges delegate.